# 求从顶点v到其他顶点的路径

class Path:
    def __init__(self, graph, v):
        self.graph = graph
        self.visited = [False for _ in range(graph.V())]
        # 记录上一个顶点
        self.parent = [-1 for _ in range(graph.V())]
        
        self.dfs(v)
        
    def dfs(self, v):
        self.visited[v] = True
        # 这里局限于使用连接表表示的图
        for u in self.graph.edges(v):  # 遍历所有邻边
            if not self.visited[u]:
                # 顶点v是从u过来的
                self.parent[u] = v
                self.dfs(u)
    
    # 使用存在一条路径从v到u
    def has_path(self, u):
        assert u >= 0 and u < self.graph.V()
        return self.visisted[u]
    
    def path(self, u):
        stack = []
        w = u 
        while w != -1:
            stack.append(w)
            w = self.parent[w]
        
        return stack[::-1]
    
if __name__ == '__main__':
    from graph import build_graph

    # 参考示例2.png中的第一个图
    graph = build_graph('path.txt', 7)
    p = Path(graph, 0)
    result = p.path(6)
    result = '->'.join([str(i) for i in result])
    print("从顶点0到顶点6的路径为:", result)